package link_list

type Node struct {
     Val int
     Next *Node
     Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	cur := head
	var nextTmp *Node
	// 插入新节点
	for cur != nil {
		nextTmp = cur.Next
		cur.Next = &Node{Val: cur.Val}
		cur.Next.Next = nextTmp
		cur = nextTmp
	}
	// 拷贝random指针
	cur = head
	var curCopy *Node
	for cur != nil {
		nextTmp = cur.Next.Next
		curCopy = cur.Next
		if cur.Random != nil {
			curCopy.Random = cur.Random.Next
		}
		cur = nextTmp
	}
	// 拆分链表
	copyHead := head.Next
	cur = head
	for cur != nil {
		nextTmp = cur.Next.Next
		curCopy = cur.Next
		cur.Next = curCopy.Next
		if nextTmp != nil {
			curCopy.Next = nextTmp.Next
		}
		cur = nextTmp
	}
	return copyHead
}
